/*
 输入正整数k，找到所有的正整数x≥y，使得1/k = 1/x +1/y。
 样例输入：
 2
 12
 样例输出：
 2
 1/2 = 1/6 + 1/3
 1/2 = 1/4 + 1/4
 8
 1/12 = 1/156 + 1/13
 1/12 = 1/84 + 1/14
 1/12 = 1/60 + 1/15
 1/12 = 1/48 + 1/16
 1/12 = 1/36 + 1/18
 1/12 = 1/30 + 1/20
 1/12 = 1/28 + 1/21
 1/12 = 1/24 + 1/24
 ----------------------------------------------------------------------------------
 分析：由于x≥y，有1/x≤1/y，因此1/k - 1/y ≤ 1/y，即y≤2k。这样，只需要在k+1~2k范围之内枚举y，然后根据y尝试计算出x即可。
 此处我将x的区间设置为2k~(2k)^2/2。算法的计算量太大，不支持超过300后的数(耗时太长)。
 */
package com.yuan.algorithms.Algorithm_2;

import java.util.Scanner;

public class 枚举_分数拆分 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int k = sc.nextInt();
            int[][] result = new int[10000][2];
            int tab1 = 0, tab2 = 0;
            int sum = 0;//记录解的个数
            for (int y = k + 1; y <= 2 * k; y++) {
                for (int x = 2 * k; x <= (int) Math.pow(2 * k, 2)/2; x++) {
                    if (fraction(k, x, y) == 1) {
                        sum++;
                        result[tab1][tab2++] = x;
                        result[tab1++][tab2--] = y;
                    }
                }
            }
            //输出结果
            System.out.println(sum);
            for (int i = 0; i < sum; i++) {
                System.out.println("1/" + k + " = " + "1/" + result[i][0] + " + 1/" + result[i][1]);
            }
        }
    }

    /**
     * 获得两个整数的最小公倍数
     *
     * @param x
     * @param y
     * @return int
     */
    public static int commonFactor(int x, int y) {
        int temp = -1;
        int a = x, b = y;
        while (temp != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }
        return x * y / a;
    }

    /**
     * 判断1/x+1/y=1/target,等于返回1，大于返回0，小于返回-1
     *
     * @param target
     * @param x
     * @param y
     * @return int
     */
    public static int fraction(int target, int x, int y) {
        int numeratorX = 1, numeratorY = 1;//分子
        int denominator = commonFactor(x, y);//分母
        numeratorX = denominator / x;
        numeratorY = denominator / y;
        //判断结果是否相等并且有效
        if (denominator / (numeratorX + numeratorY) == target && denominator % (numeratorX + numeratorY) == 0) {
            return 1;
        } else if (denominator / (numeratorX + numeratorY) > target) {
            return -1;
        } else {
            return 0;
        }

    }
}
